As data networks proliferate, and the number of ports on typical network devices grow, the size of forwarding tables may require expansion as well. In many such devices (e.g., switches or routers), the expansion of these forwarding tables may present challenges. A first challenge is that the lookup of an address in a forwarding database may take longer in a larger database, other factors being equal. Moreover, as transmission speeds increase, network devices must switch the data traffic at a faster rate to keep up with the inflow.
Network devices may employ various lookup mechanisms in order to switch data traffic in an efficient manner. Such devices may create forwarding tables that associate specific destination addresses (e.g., Medium Access Control (MAC) addresses, Virtual Local Area Network (VLAN) identifiers, etc.) with certain egress ports on the device. These forwarding tables may be indexed using a hash of each destination address entry. To lookup an address, a device may perform a hash function on a destination address of a data packet to be forwarded. The generated hash may then be matched to a hash entry in the forwarding table.
A hash function typically transforms a string of data into a fixed length value, or key, representing the original string. The fixed length is typically shorter than the original string. Hashing may be used to index and retrieve items because it is often faster to lookup an item using a shorter hashed key than it is to use the original string. Hashing may, therefore, provide efficiencies in a forwarding database.
However, as forwarding tables expand, the likelihood of hash collisions may increase as well. A hash collision occurs when two distinct inputs into a hash function produce identical outputs. As the number of destination addresses in a forwarding database grow, there is an increasing likelihood that more lookup keys will be mapped to identical indices. If the fixed length value of the hash function is increased to minimize collisions, the lookups may take longer. There is, thus, a need in the art for more efficient lookup mechanisms for forwarding tables in network devices.